package com.hl.algor_data_struct.sort;

import java.util.Arrays;

/**
 * Created by yuanhailong on 2021/10/23.
 * 选择排序：选择排序原理
 *    如果集合有N个元素，拿第一个元素跟后面所有的元素对比，找到最小的元素，然后将最小的元素的位置和第一个元素的位置对比，一次类推
 *
 *
 * 时间复杂度O(N2)  空间复杂度O(1)
 */
public class SelectionSort {

    public static void selectionSort(int[] arr){

        if(arr==null || arr.length<=1){
            return;
        }


        //第一个循坏，每个元素都要和数组中所有元素进行比较
        for(int i=0;i<arr.length;i++){
            //记录元素最小位置
            int minIndex=i;
            //每次是跟I 后面的元素进行比较 ，所以j的寻从i+1次开始。因为每次交换后I前面的一定是排好序的
            for(int j=i+1;j<arr.length;j++){
                //判断元素最小的位置
                minIndex=arr[minIndex]<arr[j]?minIndex:j;
            }
            //元素进行交换
            swap(minIndex,i,arr);
        }


        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }



    }


    /**
     * 元素进行交换
     * @param minIndex   计算出的最小所以位置
     * @param curIndex   当前元素位置
     * @param arr        原始数组
     */
    private static void swap(int minIndex,int curIndex,int arr[]){
        //当前元素的位置先记录下来
        int tmp = arr[curIndex];
        //当前元素位置替换为最小元素
        arr[curIndex]=arr[minIndex];
        arr[minIndex]=tmp;
    }




    public static void main(String[] args) {

        selectionSort(SortConstants.sortArr);
    }


}
